package com.lwx.leetcode.offer.dp;

import java.util.Arrays;

//二维动态规划问题
public class Offer13 {
    public static void main(String[] args) {
        Offer13 o = new Offer13();
//        int[][] arr = {{1, 2}, {3, 4}};
//        l = arr.length;
//        w = arr[0].length;
//        visited = new boolean[l][w];
//        for (int i = 0; i < arr.length; i++) {
//            for (int j = 0; j < arr[0].length; j++) {
//                o.movedfs(i, j);
//            }
//        }
        int ret = o.movingCount(2, 3, 1);
        System.out.println(ret);
    }

    static int l;
    static int w;
    private int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static boolean[][] visited;

    public int movingCount(int m, int n, int k) {

        int ret = 0;
        boolean[][] dp = new boolean[m][n];
//        Arrays.fill(dp, false);
//        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (lessThanK(i, j, k)) {
                    dp[i][j] = true;
                }
            }
        }
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j]) {
                    ret++;
                }
            }
        }
        return ret;
    }

    /**
     * 是否在矩阵之内
     *
     * @param m
     * @param n
     * @return
     */
    public boolean inArea(int m, int n) {
        if (m >= 0 && m < l && n >= 0 && n < w) {
            return true;
        }
        return false;
    }


    /**
     * 各个位数之和是否小于k
     *
     * @param m
     * @param n
     * @return
     */
    public boolean lessThanK(int m, int n, int k) {
        int sum = 0;
        while (m >= 10) {
            sum += m % 10;
            m = m / 10;
        }
        if(m < 10){
            sum += m;
        }
        while (n >= 10) {
            sum += n % 10;
            n = n / 10;
        }
        if(n <10){
            sum += n;
        }
        if (sum <= k) {
            return true;
        } else {
            return false;
        }
    }


    public void movedfs(int x, int y) {
        if (inArea(x, y) && !visited[x][y]) {
            System.out.print("(" + x + "," + y + ")->");
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int startNewX = x + direction[i][0];
                int startNewY = y + direction[i][1];
                movedfs(startNewX, startNewY);
//                if(inArea(startNewX,startNewY) && !visited[startNewX][startNewY]){
//                }
            }
        }
        return;
    }
}
